package previous.Test_0203;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
 * Created with Intellij IDEA
 * Description:
 * User: 星辰
 */
public class Solution {
    public void swap(int[] n,int i ,int j){
        int t=0;
        t=n[i];
        n[i]=n[j];
        n[j]=t;
    }
    public int[] inventoryManagement(int[] stock, int cnt) {
        qsort(stock, 0, stock.length - 1, cnt);
        int[] ret=new int[cnt];
        for (int i = 0; i < cnt; i++) {
            ret[i]=stock[i];
        }
        return ret;
    }
    public void qsort(int[] nums,int l,int r,int k){
        if(l>=r){
            return ;
        }
        int left=l-1;
        int right=r+1;
        Random random=new Random();
        int key=nums[random.nextInt(r-l+1)+l];
        for (int i = l; i <right ; ) {
            if(nums[i]<key){
                swap(nums,++left,i++);
            }else if(nums[i]==key){
                i++;
            }else{
                swap(nums,--right,i);
            }
        }
        int a=left-l+1;
        int b=right-left-1;
        if(a>=k){
            qsort(nums,l,left,k);
        }else if(a+b>=k){
            return;
        }else
            qsort(nums,right,r,k-a-b);

    }
    //归并排序
    public int[] sortArray(int[] nums) {
         merge(nums,0,nums.length-1);
         return nums;
    }
    public void merge(int[] nums,int left,int right){
        if(left>=right){
            return ;
        }
        int mid=(right+left)/2;
        //分解
        merge(nums,left,mid);
        merge(nums,mid+1,right);
        //合并
        int[] tmp=new int[right-left+1];
        int i=0;
        int cur1=left,cur2=mid+1;
        while(cur1<=mid && cur2<=right){
            if(nums[cur1]<=nums[cur2]){
                tmp[i++]=nums[cur1++];
            }else{
                tmp[i++]=nums[cur2++];
            }
        }
        while(cur1<=mid){
            tmp[i++]=nums[cur1++];
        }
        while(cur2<=right){
            tmp[i++]=nums[cur2++];
        }
        for (int j = 0; j < i; j++) {
            nums[j+left]=tmp[j];
        }
    }
    //交易逆序对的总数
    public int reversePairs(int[] record) {
        return mergeSort(record,0,record.length-1);
    }

    public int mergeSort(int []nums,int left,int right) {
        if(left>=right){
            return 0;
        }
        int[] tmp=new int[right-left+1];
        int mid=(right+left)/2;
        int ret=0;
        //分解
        ret +=mergeSort(nums,left,mid);
        ret +=mergeSort(nums,mid+1,right);
        //合并
        int i=0;
        int cur1=left;
        int cur2=mid+1;
        while(cur1<=mid && cur2<=right){
            if(nums[cur1]<=nums[cur2]){
                tmp[i++]=nums[cur2++];

            }else{
                tmp[i++]=nums[cur1++];
                ret+=right-cur2+1;
            }
        }
        while(cur1<=mid){
             tmp[i++]=nums[cur1++];
        }
        while(cur2<=right){
            tmp[i++]=nums[cur2++];
        }
        for (int j = 0; j < i; j++) {
            nums[j+left]=tmp[j];
        }
        return ret;
    }
    //计算右侧小于当前元素个数
    int[] ret;
    int[] index;
    int[] tmpIndex;
    public List<Integer> countSmaller(int[] nums) {
         int len=nums.length;
         ret=new int[len];
        index=new int[len];
        tmpIndex=new int[len];
        for (int i = 0; i < len; i++) {
            index[i]=i;
        }
           mergeSort1(nums,0,len-1);
           List<Integer> list=new ArrayList<>();
        for (int i = 0; i < len; i++) {
            list.add(ret[i]);
        }
        return list;
    }
    public void mergeSort1(int []nums,int left,int right){
        if(left>=right){
            return ;
        }
        int[] tmp=new int[right-left+1];
        int mid=(right+left)/2;
        //分解
        mergeSort1(nums,left,mid);
        mergeSort1(nums,mid+1,right);
        //合并
        int i=0;
        int cur1=left;
        int cur2=mid+1;
        while(cur1<=mid && cur2<=right){
            if(nums[cur1]<=nums[cur2]){
                tmpIndex[i]=index[cur2];
                tmp[i++]=nums[cur2++];
            }else{
                ret[index[cur1]]+=right-cur2+1;
                tmpIndex[i]=index[cur1];
                tmp[i++]=nums[cur1++];

            }
        }
        while(cur1<=mid){
            tmpIndex[i]=index[cur1];
            tmp[i++]=nums[cur1++];
        }
        while(cur2<=right){
            tmpIndex[i]=index[cur2];
            tmp[i++]=nums[cur2++];
        }
        for (int j = 0; j < i; j++) {
            index[j+left]=tmpIndex[j];
            nums[j+left]=tmp[j];
        }
    }
}
